Intervals
https://leetcode.com/problems/insert-interval
# Greedy
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
res = []
for i in range(len(intervals)):
if newInterval[1] < intervals[i][0]:
res.append(newInterval)
return res + intervals[i:]
elif newInterval[0] > intervals[i][1]:
res.append(intervals[i])
else:
newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
res.append(newInterval)
return res
# Search and insert
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
insertPos = 0
res = []
# Search for insert position and add intervals if possible
while insertPos < len(intervals) and intervals[insertPos][1] < newInterval[0]:
res.append(intervals[insertPos])
insertPos += 1
# Resolve overlapping
while insertPos < len(intervals) and newInterval[1] >= intervals[insertPos][0]:
newInterval = [
min(intervals[insertPos][0], newInterval[0]),
max(intervals[insertPos][1], newInterval[1])
]
insertPos += 1
res.append(newInterval)
res += intervals[insertPos:]
return res
https://leetcode.com/problems/merge-intervals
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
res = [intervals[0]]
for start, end in intervals[1:]:
curInterval = res[-1]
if start > curInterval[1]:
res.append([start, end])
else:
curInterval = [min(curInterval[0], start), max(curInterval[1], end)]
res[-1] = curInterval
return res
https://leetcode.com/problems/non-overlapping-intervals
- Intuition: If we sort by start time: [1,7], [1,3], [2,3], [3,4], [4,5] If we tried the greedy approach of keeping the first interval we see after sorting by start time, we'd keep [1,7] and have to remove ALL other intervals because they overlap with it. The answer would be 4 removals.
If we sort by end time instead: [2,3], [1,3], [3,4], [4,5], [1,7] Now we can keep [2,3], then [3,4], then [4,5] - only needing to remove [1,3] and [1,7]. The answer is 2 removals.
The key insight is that sorting by end time guarantees that when we keep an interval, we're committing to the shortest possible blockage of future space. When we kept [1,7] in the start-time approach, we made a bad choice because we committed to blocking a huge range unnecessarily. By sorting on end time, we ensure we always make the most conservative choice about how much future space we block. This is why sorting by start time fails - it doesn't give us any guarantee about how much future space we might accidentally block with our choices
A good way to decide: Ask yourself "Do I care more about when things begin happening (use start) or when they finish (use end)?" If you need to track ongoing events or merge things, sort by start. If you need to make optimal choices about which intervals to pick, sort by end.
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[1])
lastEnd = intervals[0][1]
count = 0
for start, end in intervals[1:]:
if start >= lastEnd:
lastEnd = end
else:
count += 1
return count
https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons
def findMinArrowShots(self, points: List[List[int]]) -> int:
points.sort(key=lambda t: t[1])
arrow = 1
lastArrowPos = points[0][1]
for start, end in points:
if start > lastArrowPos:
arrow += 1
lastArrowPos = end
return arrow
https://leetcode.com/problems/car-pooling
https://leetcode.com/problems/meeting-rooms
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
if not intervals:
return True
intervals.sort()
prevEnd = intervals[0][1]
for start, end in intervals[1:]:
if start < prevEnd:
return False
prevEnd = max(prevEnd, end)
return True
https://leetcode.com/problems/meeting-rooms-ii